주어진 해가 알려지지 않은 상태에서 해를 얻기 쉬운 형태로 변형을 진행하는 가우스 소거법과 유사하게 동작

3 단계로 구성된 반복(iteration)마다 목적함수 값이 향상되는 새로운 기저가능해를 구한다.

반복과정에서 더이상 값이 향상될 수 없을 때까지 수행한다.

현재의 기저가능해가 최적인지를 판단(선형-프로그램의 쌍대성을 이용)

최대값은 최소비율을 계산하여 결정한다.

진입 변수와 진출 변수 사이의 역할을 변환